
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1634. -- [Usaco2007 Jan]Protecting the Flowers -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1634: [Usaco2007 Jan]Protecting the Flowers</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>234&nbsp;&nbsp;<span class=green>Solved: </span>129<br>[<a href='submitpage.php?id=1634'>Submit</a>][<a href='problemstatus.php?id=1634'>Status</a>][<a href='bbs.php?id=1634'>Discuss</a>]</center><h2>Description</h2><div class=content>Farmer John went to cut some wood and left N (2 <= N <= 100,000)
cows eating the grass, as usual. When he returned, he found to his
horror that the cows were in his garden eating his beautiful flowers.
Wanting to minimize the subsequent damage, FJ decided to take
immediate action and transport the cows back to their barn.

Each cow i is at a location that is Ti minutes (1 <= Ti <= 2,000,000)
away from the barn. Furthermore, while waiting for transport, she
destroys Di (1 <= Di <= 100) flowers per minute. No matter how hard
he tries,FJ can only transport one cow at a time back to the barn.
Moving cow i to the barn requires 2*Ti minutes (Ti to get there and
Ti to return).

Write a program to determine the order in which FJ should pick up
the cows so that the total number of flowers destroyed is minimized.

//有六头牛，下面六行给出每头牛回家的路所要花的时间，以及它在每个时间摧毁花的数目
//John每次送一头牛回家，再返回来.希望将所有牛都送回家，然后被摧的花的总数最少.
</div><h2>Input</h2><div class=content>* Line 1: A single integer N

* Lines 2..N+1: Each line contains two space-separated integers, Ti
        and Di, that describe a single cow's characteristics

</div><h2>Output</h2><div class=content>* Line 1: A single integer that is the minimum number of destroyed
        flowers
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>6<br />
3 1<br />
2 5<br />
2 3<br />
3 2<br />
4 1<br />
1 6<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>86<br />
<br />
OUTPUT DETAILS:<br />
<br />
FJ returns the cows in the following order: 6, 2, 3, 4, 1, 5. While<br />
he is transporting cow 6 to the barn, the others destroy 24 flowers;<br />
next he will take cow 2, losing 28 more of his beautiful flora. For<br />
the cows 3, 4, 1 he loses 16, 12, and 6 flowers respectively. When<br />
he picks cow 5 there are no more cows damaging the flowers, so the<br />
loss for that cow is zero. The total flowers lost this way is 24 +<br />
28 + 16 + 12 + 6 = 86.<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver'>Silver</a></p></div><center>[<a href='submitpage.php?id=1634'>Submit</a>][<a href='problemstatus.php?id=1634'>Status</a>][<a href='bbs.php?id=1634'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
